package dp.二维数组;


import java.util.Arrays;

/**
 * https://leetcode.cn/problems/longest-common-subsequence/
 *
 * 题解：https://mp.weixin.qq.com/s?__biz=MzAxODQxMDM0Mw==&mid=2247487860&idx=1&sn=f5759ae4f22f966db8ed5a85821edd34&scene=21#wechat_redirect
 */
public class _1143_最长公共子序列 {

    public static void main(String[] args) {
        String text1 = "abcde";
        String text2 = "ace";

        _1143_最长公共子序列 _1143_最长公共子序列 = new _1143_最长公共子序列();
        int result = _1143_最长公共子序列.longestCommonSubsequence(text1,text2);
        System.out.println(result);
    }

    /**
     * 假设2个序列分别是nums1和nums2，i属于1到nums1，j属于1到nums2
     *
     * dp(i,j)是nums1的前i个元素和nums2的前j个元素的最长公共子序列
     *
     * dp方程：
     *  if(nums1[i] = nums2[j]) ,则dp(i,j) = dp(i-1,j-1) + 1;
     *  if(nums1[i] != nums[j]), 则dp(i,j) = Max(dp(i-1,j),dp(i,j-1);
     *
     * 注意点：dp的边界条件
     * @param text1
     * @param text2
     * @return
     */
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(),n = text2.length();
        // 备忘录值为 -1 代表未曾计算
        meno = new int[m][n];
        for (int[] row : meno) {
            Arrays.fill(row, -1);
        }
        // 计算 s1[0..] 和 s2[0..] 的 lcs 长度
        return dp(text1, 0, text2, 0);
    }

    int[][] meno;

    // 定义：计算 s1[i..] 和 s2[j..] 的最长公共子序列长度
    private int dp(String s1, int i, String s2, int j) {
        // base case
        if (i == s1.length() || j == s2.length() ) return 0;

        if (meno[i][j] != -1) {
            return meno[i][j];
        }
        // 根据 s1[i] 和 s2[j] 的情况做选择
        if (s1.charAt(i) == s2.charAt(j)) {
            meno[i][j] = 1 + dp(s1, i + 1, s2, j + 1);
        } else {
            // s1[i] 和 s2[j] 至少有一个不在 lcs 中
            meno[i][j] = Math.max(dp(s1, i + 1, s2, j), dp(s1, i, s2, j + 1));
        }

        return meno[i][j];
    }
}
